package com.cn.codebrush.数组.回溯;

import java.util.ArrayList;
import java.util.List;

public class No131分割回文串 {
    public static void main(String[] args) {
        System.out.println(partition("aaa"));
    }

    static List reslist = new ArrayList();
    public static List<List<String>> partition(String s) {
        partitionHelper(s,0,new ArrayList());
        return reslist;
    }

    public static void partitionHelper(String s,int start,List list) {
        if(start == s.length()){
            reslist.add(new ArrayList<>(list));
            return;
        }

        for(int i=start;i<s.length();i++){
            String temp = s.substring(start,i+1);
            if(check(temp)){
                list.add(temp);
                partitionHelper(s,i+1,list);
                list.remove(list.size()-1);
            }
        }
    }

    public static boolean check(String s) {
        int left=0;
        int right = s.length()-1;
        while(left<right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}
